#include "BTreeNode.h"
#include "Bruinbase.h"

using namespace std;

//--------------------------------------------------- Troy

// Leaf node constructor
BTLeafNode::BTLeafNode()
{
	// Zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);

	// Initialize next node pointer to -1
	int nextNodePtr = -1;
	memcpy(buffer + NEXT_NODE_PTR_OFFSET, &nextNodePtr, sizeof(int));
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	// Sanity check: is pid even valid?
	if(pid < 0 || pid > (pf.endPid() - 1))
		return RC_INVALID_PID;
	
	// Zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
	
	// Read page file into buffer
	if(pf.read(pid, (void *) buffer) != 0)
		return RC_FILE_READ_FAILED;
	
	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	// Sanity check: is pid even valid?
	if(pid < 0)
		return RC_INVALID_PID;
	
	// Write buffer into page file
	if(pf.write(pid, (const void *) buffer) != 0)
		return RC_FILE_WRITE_FAILED;
	
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int numKeys = 0;
	
	// Copy number of keys from its offset in the buffer
	memcpy(&numKeys, buffer + NUM_KEY_OFFSET, sizeof(int));
	
	return numKeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int numKeys = getKeyCount();
	int i, tmp = 0, pos = 0;
	char *buf;

	// Copy nextNodePtr to restore later
	PageId next = getNextNodePtr();
	
	// If node is full, return error code
	if(numKeys == MAX_NUM_KEY)
		return RC_NODE_FULL;
	
	// Otherwise, find correct place to insert key, rid pair
	else
	{
		// Save old buffer in temporary buffer
		buf = new char [PageFile::PAGE_SIZE];
		memcpy(buf, buffer, PageFile::PAGE_SIZE);
		
		// Find entry id of key
		if(locate(key, i) != 0)
			i = numKeys;

		// Mark position to insert key; if key > all keys in node, it will be added at the end
		pos = i * SIZE_RID_KEY_PAIR;
		
		// Insert rid into buffer and move position forward
		memcpy(buffer + pos, &rid, sizeof(RecordId));
		pos += sizeof(RecordId);
		
		// Insert key into buffer and move position forward
		memcpy(buffer + pos, &key, sizeof(int));
		pos += sizeof(int);
		
		// Copy remaining part of old buffer to new buffer
		memcpy(buffer + pos, buf + pos - sizeof(RecordId) - sizeof(int), PageFile::PAGE_SIZE - pos);
		
		// Restore nextNodePtr in buffer
		memcpy(buffer + NEXT_NODE_PTR_OFFSET, &next, sizeof(PageId));
		
		// Increment number of keys in node and store in buffer
		numKeys++;
		memcpy(buffer + NUM_KEY_OFFSET, &numKeys, sizeof(int));
	}
	
	delete [] buf;
	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	int i, j, pos, curKey = 0, tmpKey = 0;
	bool inserted = false;
	RecordId tmpRid;
	
	// Save number of keys and next node pointer
	int numKeys = getKeyCount();
	PageId nextNodePtr = getNextNodePtr();
	
	// Calculate offset to split node
	int split = (numKeys + 2) / 2 - 1;
	
	// Sort keys into temporary buffer
	char * tmp = new char[2 * PageFile::PAGE_SIZE];
	memset(tmp, 0, 2 * PageFile::PAGE_SIZE);

	// If key should be inserted at the end
	if(locate(key, i) != 0)
	{
		// Copy entire buffer to temporary buffer
		memcpy(tmp, buffer, PageFile::PAGE_SIZE);
		
		// Find the end of buffer
		pos = numKeys * SIZE_RID_KEY_PAIR;
		
		// Copy key, rid pair to the end of temporary buffer
		memcpy(tmp + pos, &rid, sizeof(RecordId));
		pos += sizeof(RecordId);
		
		memcpy(tmp + pos, &key, sizeof(int));
	}
	
	// Otherwise, key should be inserted in the middle
	else
	{
		// Find its target position in buffer
		pos = i * SIZE_RID_KEY_PAIR;
		
		// Copy old buffer up to that point into temporary buffer
		memcpy(tmp, buffer, pos);
		
		// Copy key, rid pair into this position of temporary buffer
		memcpy(tmp + pos, &rid, sizeof(RecordId));
		pos += sizeof(RecordId);
		
		memcpy(tmp + pos, &key, sizeof(int));
		pos += sizeof(int);
		
		// Copy the rest of the old buffer into the temporary buffer
		memcpy(tmp + pos, buffer + i * SIZE_RID_KEY_PAIR, PageFile::PAGE_SIZE - pos);
	}
	
	// Insert values starting at split from temporary buffer into sibling
	for(j = split; j < numKeys + 1; j++)
	{
		pos = j * SIZE_RID_KEY_PAIR;
		
		memcpy(&tmpRid, tmp + pos, sizeof(RecordId));
		pos += sizeof(RecordId);
		
		memcpy(&tmpKey, tmp + pos, sizeof(int));
		
		if(sibling.insert(tmpKey, tmpRid) != 0)
			return -1;	// No specified error code, so just return -1
	}
	
	// Get first key in sibling and store it in siblingKey
	if(sibling.readEntry(0, siblingKey, tmpRid) != 0)
		return -1;	// No specified error code, so just return -1
	
	// Set all values after split to 0 in original buffer
	memset(buffer + split * SIZE_RID_KEY_PAIR, 0, PageFile::PAGE_SIZE - split * SIZE_RID_KEY_PAIR);
	
	// Restore nextNodePtr in buffer
	memcpy(buffer + NEXT_NODE_PTR_OFFSET, &nextNodePtr, sizeof(PageId));
		
	// Set number of keys and store in buffer
	memcpy(buffer + NUM_KEY_OFFSET, &split, sizeof(int));

	delete [] tmp;
	
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int i, pos = 0;
	int key = 0;
	int numKeys = getKeyCount();

	// TODO: use binary search instead? 
	// Start at first key and skip over key/record id's at each iteration
	for(i = 0; i < numKeys; i++)
	{
		// Get position of key in buffer
		pos = i * SIZE_RID_KEY_PAIR + sizeof(RecordId);
		
		// Copy value from buffer as an int
		memcpy(&key, buffer + pos, sizeof(int));
		
		// If key is greater than or equal to the search key, i is the correct eid
		if(key >= searchKey)
			break;
	}

	// Set eid to the correct eid if found, else set it to -1 and return error code
	if(i < numKeys)
		eid = i;
	else
	{
		eid = -1;
		return RC_NO_SUCH_RECORD;
	}
		
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	// If entry id is invalid, return an error code
	if(eid < 0 || eid > getKeyCount())
		return RC_NO_SUCH_RECORD;
	
	// Find position of entry
	int entry = eid * SIZE_RID_KEY_PAIR;

	if(entry >= LAST_LEAF_KEY_OFFSET)
		return RC_NO_SUCH_RECORD;
	
	// Copy record id from buffer
	memcpy(&rid, buffer + entry, sizeof(RecordId));
	
	// Copy key from buffer
	memcpy(&key, buffer + entry + sizeof(RecordId), sizeof(int));
	
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId nextNodePtr = 0;
	
	// Copy pid of next sibling from its offset in the buffer
	memcpy(&nextNodePtr, buffer + NEXT_NODE_PTR_OFFSET, sizeof(PageId));
	return nextNodePtr; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	// Sanity check, is pid even valid?
	if(pid < -1)
		return RC_INVALID_PID;
	
	// Copy pid to nextNodePtr position in buffer
	memcpy(buffer + NEXT_NODE_PTR_OFFSET, &pid, sizeof(PageId));
	
	return 0;
}

//--------------------------------------------------- Edvin

// NonLeaf node constructor
BTNonLeafNode::BTNonLeafNode()
{
	// Zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	// Sanity check: pid validation
	if(pid < 0 || pid > (pf.endPid() - 1))	
		return RC_INVALID_PID;
	
	// Zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);
	
	// Read page file into buffer
	if(pf.read(pid, (void *) buffer) != 0)
		return RC_FILE_READ_FAILED;

	return 0; 
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	// Sanity check: pid validation
	if(pid < 0)		
		return RC_INVALID_PID;
	
	// Write buffer into page file
	if(pf.write(pid, (const void *) buffer) != 0)		
		return RC_FILE_WRITE_FAILED;
	
	return 0; 
}
  
/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int numKeys = 0;
	
	// Copy number of keys from its offset in the buffer
	memcpy(&numKeys, buffer + NUM_KEY_OFFSET, sizeof(int));
	
	return numKeys;
}

 /*
 * Set the number of nodes at the end
 */
RC BTNonLeafNode::setNumKeys(int num)
{
	memcpy(buffer + NUM_KEY_OFFSET, &num, sizeof(int));
}

 /*
 * Read the (key) from the eid entry.
 * @param eid[IN] the entry number to read the (key)  from
 * @param key[OUT] the key from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::readKey(int eid, int& key) 
{
	// If entry id is invalid, return an error code
	if(eid < 0 || eid > getKeyCount())	
		return RC_NO_SUCH_RECORD;

	// Find position of entry
	int entry = eid * SIZE_PID_KEY_PAIR;
	
	// Copy key from buffer
	memcpy(&key, buffer + entry + sizeof(PageId), sizeof(int));
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateSlot(int searchKey, int& eid)
{ 
	int i, pos = 0;
	int key = 0;
	int numKeys = getKeyCount();
	
	// find a key that is bigger or equal to searchKey
	// Start at first key and skip over key/record id's at each iteration
	for(i = 0; i < numKeys; i++)
	{		
		// Get position of key in buffer
		pos = i * SIZE_PID_KEY_PAIR + sizeof(PageId);
		
			// Copy value from buffer as an int
		memcpy(&key, buffer + pos, sizeof(int));
		
		// If key is greater than or equal to the search key, i is the correct eid
		if(key >= searchKey)
			break;
	}

	// Set eid to the correct eid if found, else set it to -1 and return error code
	if(i < numKeys)
		eid = i;
	else
	{		
		eid = -1;
		return RC_NO_SUCH_RECORD;
	}
		
	return 0;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)	
{ 
	int numKeys = getKeyCount();
	int i, tmp = 0, pos = 0;
	char *buf;
	
	// If node is full, return error code
	if(numKeys == MAX_NONLEAF_NUM_KEY)
		return RC_NODE_FULL;
	
	// Otherwise, find correct place to insert key, pid pair
	else
	{
		// Save old buffer in temporary buffer
		buf = new char [PageFile::PAGE_SIZE];
		memcpy(buf, buffer, PageFile::PAGE_SIZE);
		
		// Find entry id of key
		if(locateSlot(key, i) != 0)
			i = numKeys;

		// Mark position to insert key; if key > all keys in node, it will be added at the end
		pos = i * SIZE_PID_KEY_PAIR + sizeof(PageId);
		
		// Insert key into buffer and move position forward
		memcpy(buffer + pos, &key, sizeof(int));
		pos += sizeof(int);
		
		// Insert pid into buffer and move position forward
		memcpy(buffer + pos, &pid, sizeof(PageId));
		pos += sizeof(PageId);
		
		// Copy remaining part of old buffer to new buffer
		memcpy(buffer + pos, buf + pos - SIZE_PID_KEY_PAIR, PageFile::PAGE_SIZE - pos);
		
		// Increment number of keys in node and store in buffer
		numKeys++;
		memcpy(buffer + NUM_KEY_OFFSET, &numKeys, sizeof(int));
	}
	
	delete [] buf;

	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey) //lll
{ 
	// split keys using ceiling of half and shove the bigger half (starting at the offset)
	// into right side
	
	int i, pos, save_pos, shove_pos, shove_size;
	int numKeys;
	
	// Store keys into temporary buffer with double the size of page_size
	char * tmp = new char[2 * PageFile::PAGE_SIZE];
	memset(tmp, 0, 2 * PageFile::PAGE_SIZE);
		
	// If key,pid should be inserted at the end
	if(locateSlot(key, i) != 0)		 
	{	
		// Copy entire buffer to temporary buffer
		memcpy(tmp, buffer, PageFile::PAGE_SIZE);
		
		// Go to the end of the last pid(right before the number of keys are stored)
		pos = NUM_KEY_OFFSET;
		
		// Copy key, pid pair to the end of temporary buffer
		// For non-leaf nodes, the (key,pid) pair is always pushedd up, and thus
		// the pid points to a node that has bigger keys than the pushed key
		memcpy(tmp + pos, &key, sizeof(int));
		pos += sizeof(int);
			
		memcpy(tmp + pos, &pid, sizeof(PageId));
	}
	// Otherwise, key should be inserted in the middle
	else
	{												
		// Find its target position in buffer
		pos = i * SIZE_PID_KEY_PAIR + sizeof(PageId); 
		save_pos = pos;
		
		// Copy old buffer up to that point + the pid to the right 
		memcpy(tmp, buffer, pos);
		
		// Copy key, pid pair into this position of temporary buffer
		memcpy(tmp + pos, &key, sizeof(int));
		pos += sizeof(int);
			
		memcpy(tmp + pos, &pid, sizeof(PageId));
		pos += sizeof(PageId);
		
		// Copy the rest of the old buffer into the temporary buffer
		memcpy(tmp + pos, buffer + save_pos, PageFile::PAGE_SIZE - save_pos);
	}

	// get the midkey
	memcpy(&midKey, tmp + NONLEAF_SPLIT_POINT, sizeof(int));
	
	// Keep all the values before NONLEAF_SPLIT_POINT in the original node and set the rest to all 0.
	memcpy(buffer, tmp, NONLEAF_SPLIT_POINT);
	memset(buffer + NONLEAF_SPLIT_POINT, 0, PageFile::PAGE_SIZE - NONLEAF_SPLIT_POINT);

	// Update the number of keys in the buffer.
	numKeys = 63;
	memcpy(buffer + NUM_KEY_OFFSET, &numKeys, sizeof(int));
		
	// find the position and the size of data to shove to sibling node
	shove_pos = NONLEAF_SPLIT_POINT + sizeof(int); 	
	shove_size = NONLEAF_SPLIT_POINT + SIZE_PID_KEY_PAIR;
	
	// Copy all values after pos_copy to the sibling node, adn set the rest to all 0.
	memcpy(&sibling, tmp + shove_pos, shove_size); 
		
	// Update the number of key in sibling node.
	sibling.setNumKeys(64);
	
	delete [] tmp;

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int i, pos = 0;
	int key = 0;
	int numKeys = getKeyCount();

	// Start at first key and skip over key/page id's at each iteration
	for(i = 0; i < numKeys; i++)
	{
		// Get position of key in buffer
		pos = i * SIZE_PID_KEY_PAIR + sizeof(PageId);
		
		// Copy value from buffer as an int
		memcpy(&key, buffer + pos, sizeof(int));
		
		// If key is greater than or equal to the search key, i is the correct eid
		if(key >= searchKey)
			break;
	}

	// Set pid to the correct pid if found
	if(i < numKeys)
		memcpy(&pid, buffer + pos - sizeof(PageId) , sizeof(PageId));
	else
	{
		//if all the keys are < search key then set the pid to the rightmost pid
		memcpy(&pid, buffer + pos + sizeof(int) , sizeof(PageId));
	}

	return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	// zero out buffer
	memset(buffer, 0, PageFile::PAGE_SIZE);

	//place data in buffer
	memcpy(buffer, &pid1, sizeof(PageId));
	memcpy(buffer + sizeof(PageId), &key, sizeof(int));
	memcpy(buffer + SIZE_PID_KEY_PAIR, &pid2, sizeof(PageId));
	
	// must set the number of keys to 1
	int keys = 1;
	memcpy(buffer + NUM_KEY_OFFSET, &keys, sizeof(int));

	return 0; 
}
